Find numbers with even number of digits

Time: O(NLog(LogM)); Space: O(LogM); easy

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]

Output: 2

Explanation:

  • contains 2 digits (even number of digits).

  • 5 contains 3 digits (odd number of digits).

  • contains 1 digit (odd number of digits).

  • contains 1 digit (odd number of digits).

  • 96 contains 4 digits (even number of digits).

  • Therefore only 12 and 7896 contain an even number of digits.

Example 2:

Input: nums = [555,901,482,1771]

Output: 1

Explanation:

  • Only 1771 contains an even number of digits.

Notes:

  • 1 <= len(nums) <= 500

  • 1 <= nums[i] <= 10^5

Hints:

  1. How to compute the number of digits of a number?

  2. Divide the number by 10 again and again to get the number of digits.

[1]:

import bisect

class Solution1(object):
    """
    Time:  O(NLog(LogM)), N the length of nums, M is the max value of nums
    Space: O(LogM)
    """
    def __init__(self):
        M = 10**5
        self.__lookup = [0]
        i = 10
        while i < M:
            self.__lookup.append(i)
            i *= 10
        self.__lookup.append(i)

    def findNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def digit_count(n):
            return bisect.bisect_right(self.__lookup, n)

        return sum(digit_count(n) % 2 == 0 for n in nums)

[3]:

s = Solution1()
nums = [12,345,2,6,7896]
assert s.findNumbers(nums) == 2
nums = [555,901,482,1771]
assert s.findNumbers(nums) == 1

[4]:

class Solution2(object):
    """
    Time:  O(NLog(LogM)), N the length of nums, M is the max value of nums
    Space: O(LogM)
    """
    def findNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def digit_count(n):
            result = 0
            while n:
                n //= 10
                result += 1
            return result

        return sum(digit_count(n) % 2 == 0 for n in nums)

[5]:

s = Solution2()
nums = [12,345,2,6,7896]
assert s.findNumbers(nums) == 2
nums = [555,901,482,1771]
assert s.findNumbers(nums) == 1

[6]:

class Solution3(object):
    """
    Time:  O(nlogm), n the length of nums, m is the max value of nums
    Space: O(logm)
    """
    def findNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(len(str(n)) % 2 == 0 for n in nums)

[7]:

s = Solution3()
nums = [12,345,2,6,7896]
assert s.findNumbers(nums) == 2
nums = [555,901,482,1771]
assert s.findNumbers(nums) == 1